home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / zcpp_jae.zip / HASH.C < prev    next >
C/C++ Source or Header  |  1990-07-06  |  4KB  |  171 lines
  1. /*
  2.  
  3.  
  4.  Copyright (C) 1990 Texas Instruments Incorporated.
  5.  
  6.  Permission is granted to any individual or institution to use, copy, modify,
  7.  and distribute this software, provided that this complete copyright and
  8.  permission notice is maintained, intact, in all copies and supporting
  9.  documentation.
  10.  
  11.  Texas Instruments Incorporated provides this software "as is" without
  12.  express or implied warranty.
  13.  
  14.  
  15.  *
  16.  * Edit history
  17.  * Created: LGO 30-Mar-89 -- Initial design and implementation.
  18.  *
  19.  * Hash functions
  20.  */
  21.  
  22. #include "defmacio.h"
  23.  
  24. void*
  25. next_hash(h, firstp)
  26.    struct Hash_Table* h;
  27.    Boolean firstp;
  28. {
  29.   if(firstp) {
  30.     h->current_bucket = 0;
  31.     h->current_index = 0;
  32.   }
  33.   while (h->current_bucket < hash_primes[h->bucket_index]) {
  34.     if (h->current_index < h->items_in_buckets[h->current_bucket])
  35.       return h->table[h->current_bucket].data[h->current_index++].value;
  36.     else {
  37.       h->current_bucket += 1;
  38.       h->current_index = 0;
  39.     }
  40.   }
  41.   return NULL;
  42. }
  43.  
  44. /* sxhash -- Hash function for char*
  45.  * Input:    Character string
  46.  * Output:    unsigned long hash value
  47.  */
  48. unsigned long sxhash(string)
  49.   char* string;
  50. {
  51.   register unsigned long hash = *string++;
  52.   if(*string != EOS) {
  53.     hash = (hash << 7) ^ *string++;
  54.     if (*string != EOS) {
  55.       hash = (hash << 7) ^ *string++;
  56.       if (*string != EOS) {
  57.     hash = (hash << 7) ^ *string++;
  58.     while (*string != EOS) { /* rotate hash left 7 bits */
  59.       int rest = hash >> 25;
  60.       hash = ((hash << 7) | rest) ^ *string++;
  61.     }
  62.       }
  63.     }
  64.   }
  65.   return hash;
  66. }
  67.  
  68. struct Hash_Table*
  69. init_Hash_Table() {
  70.   struct Hash_Table* h = (struct Hash_Table*) getmem(sizeof(struct Hash_Table));
  71.   int prime, i;
  72.   h->entry_count = 0;    
  73.   h->bucket_index = 0;    
  74.   prime  = hash_primes[h->bucket_index];    
  75.   h->items_in_buckets = (unsigned char*) getmem (prime);    
  76.   for (i = 0; i < prime; i++)        
  77.     h->items_in_buckets[i] = 0;
  78.   h->table = (struct bucket*) getmem(sizeof(struct bucket)*prime);
  79.   return h;
  80. }
  81.  
  82. static void
  83. resize (h, n)
  84.      struct Hash_Table* h;
  85.      int n;
  86. {
  87.   unsigned char* temp1;
  88.   struct bucket* temp2;            
  89.   long old_prime, i, j, new_prime, hash;
  90.   old_prime = hash_primes[h->bucket_index];
  91.  
  92.   while (hash_primes[h->bucket_index]*BUCKET_SIZE < n)
  93.     h->bucket_index++;
  94.  
  95.  retry:
  96.   new_prime = hash_primes[h->bucket_index];
  97.   temp1 = (unsigned char*) getmem (new_prime);        
  98.   for (i = 0; i < new_prime; i++)        
  99.     temp1[i] = 0;                
  100.   temp2 = (struct bucket*) getmem(sizeof (struct bucket) * new_prime); 
  101.   for (i = 0; i < old_prime; i++) {    
  102.     for (j = 0; j < h->items_in_buckets[i]; j++) { 
  103.       char* key = h->table[i].data[j].key;
  104.       hash = sxhash(key) % new_prime;
  105.       if (temp1[hash] >= BUCKET_SIZE) {      /* Bucket Overflow */
  106.     free (temp1);
  107.     free (temp2);
  108.     h->bucket_index++;
  109.     goto retry;
  110.       }
  111.       temp2[hash].data[temp1[hash]].key = key;    
  112.       temp2[hash].data[temp1[hash]].value = h->table[i].data[j].value;    
  113.       ++temp1[hash];
  114.     }
  115.   }
  116.   free (h->items_in_buckets);
  117.   free (h->table);            
  118.   h->items_in_buckets = temp1;        
  119.   h->table = temp2;            
  120. }
  121.  
  122. int
  123. get_entry_count (h)
  124.      struct Hash_Table* h;
  125. {
  126.   return (h->entry_count);
  127. }
  128.  
  129. Boolean
  130. put_hash (h, key, value)
  131.     struct Hash_Table* h;
  132.     char* key;
  133.     void* value;
  134. {
  135.   long prime,hash;
  136.   int next, i;
  137.  retry:
  138.   prime = hash_primes[h->bucket_index];
  139.   hash = sxhash(key) % prime;
  140.   for (i = 0; i < h->items_in_buckets[hash]; i++)
  141.     if (!strcmp(key,h->table[hash].data[i].key))
  142.       return FALSE;
  143.   if (h->items_in_buckets[hash] >= BUCKET_SIZE) {
  144.     resize (h, hash_primes[h->bucket_index+1]*BUCKET_SIZE);
  145.     goto retry;
  146.   }
  147.   next = h->items_in_buckets[hash]++;
  148.   h->table[hash].data[next].key = key;
  149.   h->table[hash].data[next].value = value;
  150.   h->entry_count++;            
  151.   return TRUE;
  152. }
  153.  
  154. void*
  155. get_hash (h, key)
  156.      struct Hash_Table* h;
  157.      char* key;
  158. {
  159.   long prime, hash;
  160.   int i, len;
  161.   prime = hash_primes[h->bucket_index];
  162.   hash = sxhash(key) % prime;
  163.   len = h->items_in_buckets[hash];
  164.   for (i = 0; i < len; i++) {
  165.     if (!strcmp(key,h->table[hash].data[i].key))
  166.       return (h->table[hash].data[i].value);
  167.   }
  168.   return NULL;
  169. }
  170.  
  171.